package org.jlambda.util;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * borrowed from a microsoft paper
 * @author TGDTWCH1
 *
 */
public class GenCombinationFactoral {

	public final static int fact(int m){
		int ans = 1;
		  for (int i = m; i >= 1; --i)
		  {
		    ans = ans * i;
		  }
		return ans;
		//return numb*fact(numb-1);
	}
	
//	static void Main()
//	{
//	  long n = 4;
//	  long k = 2;
//	  Console.WriteLine("With n = " + n + ", and k = " + k);
//	  Console.WriteLine("There are " + Combination.Choose(n,k) + 
//	      "combinations\n");
//
//	  Combination c = new Combination(n,k);
//	  Console.WriteLine("The mathematical combinations are:");
//	  while (c != null)
//	  {
//	    Console.WriteLine(c.ToString());
//	    c = c.Successor();
//	  }
//	  Console.ReadLine();
//	}
//	
	static public class Combination
	{
	  private long n = 0;
	  private long k = 0;
	  private long[] data = null;

	  public Combination(long n, long k) throws Exception
	  {
	    if (n < 0 || k < 0) // normally n >= k
	      throw new Exception("Negative parameter in constructor");  
	    this.n = n;
	    this.k = k;
	    this.data = new long[(int)k];
	    for (long i = 0; i < k; ++i)
	      this.data[(int)i] = i;
	  }

	  public long[] getPositions(){
		  return data;
	  }
	  
	  public String toString()
	  {
	    StringBuilder sb = new StringBuilder();
	    sb.append("{ ");
	    for (long i = 0; i < this.k; ++i)
	      sb.append(" "+ this.data[(int)i]);
	    sb.append("}");
	    return sb.toString();
	  }
	
	public static long Choose(long n, long k) throws Exception
	{
	  if (n < 0 || k < 0)
	    throw new Exception("Invalid negative parameter in Choose()"); 
	  if (n < k) return 0;
	  if (n == k) return 1;

	  long delta, iMax;

	  if (k < n-k) // ex: Choose(100,3)
	  {
	    delta = n-k;
	    iMax = k;
	  }
	  else         // ex: Choose(100,97)
	  {
	    delta = k;
	    iMax = n-k;
	  }

	  long ans = delta + 1;

	  for (long i = 2; i <= iMax; ++i)
	  {
	    ans = (ans * (delta + i)) / i; 
	  }

	  return ans;
	}
	public Combination Successor() throws Exception
	{
	  if (this.data.length == 0 ||
	      this.data[0] == this.n - this.k)
	    return null;

	  Combination ans = new Combination(this.n, this.k);

	  long i;
	  for (i = 0; i < this.k; ++i)
	    ans.data[(int)i] = this.data[(int)i];
	 
	  for (i = this.k - 1; i > 0 && ans.data[(int)i] == this.n - this.k + i; --i) ;
	 
	  ++ans.data[(int)i];

	  for (long j = i; j < this.k - 1; ++j)
	    ans.data[(int)j+1] = ans.data[(int)j] + 1;

	  return ans;
	}
	}
	
	public static ArrayList getCombinations(int n) throws Exception {
		ArrayList fullList = new ArrayList();
		
		for(long k = 1; k<n;k++) {
			ArrayList breakDown = new ArrayList();
			Combination c = new Combination(n,k);
			while (c != null)
			{
				ArrayList row = new ArrayList(n);
				for (int i = 0; i < n; i++) {
					row.add(null);
				}
				long[] data = c.getPositions();
				for (int i = 0; i < data.length; i++) {
					row.set((int)data[i], data[i]);
				}
				breakDown.add(row);
				c = c.Successor();
			}
			fullList.add(breakDown);
		}
		return fullList;
	}

	public static void main(String[] args) throws Exception {
		ArrayList fullList = new ArrayList();
		
		long n = 4;
		ArrayList list = getCombinations((int)n);
		for (Iterator iter = list.iterator(); iter.hasNext();) {
			ArrayList element = (ArrayList) iter.next();
			for (Iterator iterator = element.iterator(); iterator.hasNext();) {
				ArrayList entries = (ArrayList) iterator.next();
				System.out.println(entries);
			}
		}
		
//		ArrayList<Number> primes = new ArrayList();
//		primes.add(2);
//		primes.add(3);
//		primes.add(5);
//		primes.add(11);
//				
//		for (Iterator iter = list.iterator(); iter.hasNext();) {
//			ArrayList element = (ArrayList) iter.next();
//			for (Iterator iterator = element.iterator(); iterator.hasNext();) {
//				ArrayList entries = (ArrayList) iterator.next();
//				int comb = 1;
//				for (Object object : entries) {
//					if (object!=null){
//						comb*=primes.get(((Number)object).intValue()).intValue();
//					}
//				}
//				System.out.println(comb);
//			}
//		}
		
		for(long k = 1; k<n;k++) {
			ArrayList breakDown = new ArrayList();
		  System.out.println("With n = " + n + ", and k = " + k);
		  System.out.println("There are " + Combination.Choose(n,k) + 
		      "combinations\n");
	
		  Combination c = new Combination(n,k);
		  System.out.println("The mathematical combinations are:");
		  while (c != null)
		  {
			  breakDown.add(c.getPositions());
			  printArray(c.getPositions());
			 // System.out.println(c.toString());
		    c = c.Successor();
		  }
		  fullList.add(breakDown);
		}
	}
	
	static public final void printArray(long array[]){
		StringBuilder builder = new StringBuilder();
		for (Long object : array) {
			builder.append(object);
			builder.append(",");
		}
		System.out.println(builder.toString());
	}
}
